1837D - Bracket Coloring - CodeForces Solution

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long int
#define endl '\n'
#define fr first
#define sd second
#define gcd __gcd
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ppc   __builtin_popcount
#define ppcll __builtin_popcountll
#define pbds tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
template<class T> ostream& operator<<(std::ostream& o,vector<T> &v){ for(auto &x : v){ o<<x<<" ";}return o;}
template<class T> ostream& operator<<(std::ostream& o,set<T> &v){ for(auto &x : v){ o<<x<<" ";}return o;}
template<class T> istream& operator>>(std::istream &o , vector<T> &v){for(int i=0;i<v.size();i++){o>>v[i];}return o;}
int mod = 1e9+7;
bool ck(string g){
    int cnt =0;
    // cout<<g<<"->";
    for(int i=0;i<g.size();i++){
        if(g[i]=='(') cnt++;
        else cnt--;
        // cout<<cnt<<" ";
        if(cnt<0) return 0;
    }
    // cout<<endl;
    return 1;
}
/*--------------------------------------------------------------*/
void kal_425() 
{
    int mn = INT64_MAX;
    int mx = INT64_MIN;
    int sum =0;
    int n;
    cin>>n;
    string s;
    cin>>s;
    int cnt=0;
    for(int i=0;i<n;i++){
        cnt+= (s[i]==')');
    }
    if(cnt != (n-cnt)){
        cout<<-1<<endl;
        return;
    }
    string g = s;
    reverse(all(g));
    if(ck(s) || ck(g)){
        cout<<1<<endl;
        for(int i=0;i<n;i++){
            cout<<1<<" ";
        }
        cout<<endl;
        return;
    }
    int i=0,j=n-1;
    vector<int> col(n,2);
    while(i<j){
        if(s[i]=='(' && s[j]==')'){
            col[i]=col[j]=1;
            i++;j--;
        }
        else if(s[i]=='('){
            j--;
        }
        else{
            i++;
        }
    }
    cout<<2<<endl;
    for(int i=0;i<n;i++){
        cout<<col[i]<<" ";
    }
    cout<<endl;
}
signed main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t = 1;
    cin>>t;
    for(int i = 1; i <= t; i++){
           //cout<<"Case #"<<i<<": ";
           kal_425();
    }
    return 0;
}